package com.techyuan.algorithm.leetcode;

/**
 * http://oj.leetcode.com/problems/decode-ways/
 * 解题思路待补充:http://blog.csdn.net/linhuanmars/article/details/24570759
 * Created by Administrator on 2017/2/17.
 */
public class DecodeWays {

    public static int numDecodings(String s) {
        char[] chArr = s.toCharArray();
        if (chArr.length == 0)
            return 0;
        int[] d = new int[chArr.length];
        d[0] = chArr[0] != '0' ? 1 : 0;

        for (int i = 1; i < chArr.length; i++) {
            if (chArr[i] == '0' && chArr[i - 1] == '0')
                return 0;
            if (chArr[i] != '0')
                d[i] += d[i - 1];
            if (!(chArr[i - 1] == '0' || (chArr[i - 1] == '2' && chArr[i] >= '7') || chArr[i - 1] > '2'))
                d[i] += (i == 1 ? 1 : d[i - 2]);
        }

        return d[chArr.length - 1];
    }

    public static void main(String[] args) {
        String s = "27";
        System.out.println("字符串:" + s + " numDecodings:" + numDecodings(s));
    }
}
